import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * 636. 函数的独占时间
 * https://leetcode-cn.com/problems/exclusive-time-of-functions/
 */
public class Solutions_636 {
    public static void main(String[] args) {
//        int n = 2;
//        String[] logArr = {"0:start:0",
//                           "1:start:2",
//                           "1:end:5",
//                           "0:end:6"};  // output: {3, 4}

//        int n = 1;
//        String[] logArr = {"0:start:0",
//                           "0:start:2",
//                           "0:end:5",
//                           "0:start:6",
//                           "0:end:6",
//                           "0:end:7"};  // output: {8}

        int n = 1;
        String[] logArr = {"0:start:0",
                           "0:start:1",
                           "0:start:2",
                           "0:end:3",
                           "0:end:4",
                           "0:end:5"};  // output: {6}

        List<String> logs = Arrays.asList(logArr);
        int[] result = exclusiveTime(n, logs);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解题思路：栈实现
     * 遇 start 则将开始时间与序号入栈
     * 遇 end 则将栈顶元素出栈（此时栈顶元素一定是最后 start 的那个序号）
     * 开始时间和序号出栈后，可以计算出该函数的占用时间 b（时间需要用累加的方式）
     * 同时，栈顶元素的独占时间减少 b 个单位（因为被占用了 b 个单位时间，那么就需要减去）
     */
    public static int[] exclusiveTime(int n, List<String> logs) {
        Deque<int[]> stack = new ArrayDeque<>();

        int[] res = new int[n];
        for (String log : logs) {
            String[] arr = log.split(":");
            int id = Integer.parseInt(arr[0]);
            int time = Integer.parseInt(arr[2]);
            if ("start".equals(arr[1])) {
                // 入栈
                stack.push(new int[]{id, time});
            } else {
                int[] temp = stack.poll();
                int i = temp[0], t = temp[1];
                // 出栈
                // 计算出独占时间
                int spend = time - t + 1;
                res[i] += spend;
                if (!stack.isEmpty()) {
                    // 栈顶序号的独占时间被序号 i 占用了 spend 个单位
                    res[stack.peek()[0]] -= spend;
                }
            }
        }
        return res;
    }
}
